package com.zlk.algorithm.algorithm.unionAndFind;

import org.junit.Test;

import java.io.*;

/**
 * @program: algorithm
 * @ClassName UnionAndFindArray
 * @description:并查集数组实现
 * @author: slfang
 * @create: 2024-03-07 14:32
 * @Version 1.0
 **/
public class UnionAndFindArray {
    public static int MAXN = 1000001;
    public  int[] father = new int[MAXN];

    public  int[] size = new int[MAXN];

    public  int[] help = new int[MAXN];

    public UnionAndFindArray(int n) {
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }


    public void union(int a,int b){
        int fatherA = findFather(a);
        int fatherB = findFather(b);
        if(fatherA!=fatherB){
            int sizeA = size[fatherA];
            int sizeB = size[fatherB];
            if(sizeA>=sizeB){
                father[fatherB] = fatherA;
                size[fatherA] += sizeB;
            }else{
                father[fatherA] = fatherB;
                size[fatherB] += sizeA;
            }
        }
    }

    private int findFather(int cur) {
        int i = 0;               //0 1 2
        while (cur!=father[cur]){//   0     1
            help[i++] = cur;// help[0]=0   help[1] = 1
            cur = father[cur];//cur=1     curr=2
        }
        i--;//i=2
        while (i>=0){
            //此处操作是为了平摊
            father[help[i--]] = cur;
        }
        return cur;
    }

    // 查询x和y是不是一个集合
    public  boolean isSameSet(int x, int y) {
        return findFather(x) == findFather(y);
    }

    @Test
    public void test1() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            UnionAndFindArray unionAndFindArray = new UnionAndFindArray(n);
            in.nextToken();
            int m = (int) in.nval;
            for (int i = 0; i < m; i++) {
                in.nextToken();
                int op = (int) in.nval;
                in.nextToken();
                int x = (int) in.nval;
                in.nextToken();
                int y = (int) in.nval;
                if (op == 1) {
                    out.println(unionAndFindArray.isSameSet(x, y) ? "Yes" : "No");
                    out.flush();
                } else {
                    union(x, y);
                }
            }
        }
    }
}
